package leetcodecompetition.D357;

import java.util.Arrays;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-08-06-11:27
 * @Description: 1.0
 */
public class T6951 {
    int[][] dir = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size();
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(arr[i], n * n);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    p(grid, i, j, 0, arr);
                }
            }
        }
        int[][] arrMax = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(arr[i], -1);
        }
        arrMax[n - 1][n - 1] = arr[n - 1][n - 1];
        return dfs(arr, 0, 0, arr[0][0], arrMax);
    }

    public void p(List<List<Integer>> grid, int x, int y, int t, int[][] arr) {
        int n = grid.size();
        if (x < 0 || y < 0 || x >= n || y >= n || arr[x][y] <= t) {
            return;
        }
        arr[x][y] = t;
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0], ty = y + dir[i][1];
            p(grid, tx, ty, t + 1, arr);
        }
    }

    public int dfs(int[][] arr, int x, int y, int t, int[][] arrMax) {
        int n = arr.length;
        if (arrMax[x][y] >= t) {
            return arrMax[x][y];
        }
        if (x==n-1||y==n-1) {
            return Math.max(arrMax[x][y],t);
        }
        if (arr[x][y] < t) {
            t = arr[x][y];
        }
        int max = -1;
        for (int i = 0; i < 4; i++) {
            int tx = x + dir[i][0], ty = y + dir[i][1];
            int p = arr[x][y];
            if (x < 0 || y < 0 || x >= n || y >= n || arr[x][y] == -1) {
                break;
            }
            arr[x][y] = -1;
            int d = dfs(arr, tx, ty, t, arrMax);
            max = Math.max(max, d);
            arr[x][y] = p;
        }
        arrMax[x][y] = max;
        return max;
    }
}
